//1793.好子数组的最大分数
//https://leetcode.cn/problems/maximum-score-of-a-good-subarray/?envType=daily-question&envId=2024-03-19
class Solution {
public:
    int maximumScore(vector<int>& nums, int k) {
        int n = nums.size();
        int left = k - 1, right = k + 1;
        int ret = 0;
        //逐渐枚举比nums[k]小的值,区间越大越好
        for (int i = nums[k];;)
        {
            //扩大两区间，找比k下标值小的
            while (left >= 0 && nums[left] >= i) --left;
            while (right < n && nums[right] >= i) ++right;
            ret = max(ret, (right - left - 1) * i);
            if (left < 0 && right >= n || i == -1) break;
            //如果区间外与当前left和right的差值很大，则会导致一直i--从而增加复杂度
            //此时我们直接将变成left和right间的较大值即可
            i = max(left<0?-1:nums[left],right>=n?-1:nums[right]);
        }
        return ret;
    }
};